/*
516. [最长回文子序列](https://leetcode.cn/problems/longest-palindromic-subsequence/description/)
 辛泽豪
*/

code：



class Solution {
public:
    // 定义两个字符数组a和b，用于存储原始字符串及其反转
    char a[1010], b[1010];

    // 定义函数longestPalindromeSubseq，计算字符串s的最长回文子序列长度
    int longestPalindromeSubseq(string s) {
        int n = s.size();  // 获取输入字符串s的长度
        int res = 0;  // 结果初始化为0
        // 初始化一个(n+1)×(n+1)大小的二维DP数组，dp[i][j]表示a前i个字符与b前j个字符的最长公共子序列长度
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

        // 将字符串s正向存储到数组a中，反向存储到数组b中
        for(int i = 0; i < n; i++){
            a[i] = s[i];  // 正序存储
            b[i] = s[n - i - 1];  // 反序存储
        }

        // 使用动态规划填充dp表
        for(int i = 1; i <= n; i++){  // 遍历a的每个字符
            for(int j = 1; j <= n; j++){  // 遍历b的每个字符
                // 如果当前字符不相等，则最长公共子序列等于上一行或左边一列的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                // 如果当前字符相等，则最长公共子序列等于左上角的值加1
                if(a[i - 1] == b[j - 1]){
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }

        // dp[n][n]即为整个字符串s与其反转字符串的最长公共子序列长度，也就是最长回文子序列的长度
        return dp[n][n];
    }
};